
"""
543. 二叉树的直径
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.max_depth = 0

    def diameterOfBinaryTree1(self, root: Optional[TreeNode]) -> int:
        self.traverse(root)
        return self.max_depth

    '''遍历二叉树，获取直径'''
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return

        # 获取最大直径
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        self.max_depth = max(self.max_depth, left + right)

        # 前序位置
        self.traverse(root.left)
        # 中序位置
        self.traverse(root.right)
        # 后序位置

    '''遍历二叉树，获取最大深度'''
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 前序位置
        left = self.maxDepth(root.left)
        # 中序位置
        right = self.maxDepth(root.right)
        # 后序位置
        return max(left, right) + 1

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.maxDepth1(root)
        return self.max_depth

    '''遍历二叉树，获取最大深度'''
    def maxDepth1(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 前序位置
        left = self.maxDepth1(root.left)
        # 中序位置
        right = self.maxDepth1(root.right)

        self.max_depth = max(self.max_depth, left + right)

        # 后序位置
        return max(left, right) + 1